1. Field of the Invention
The present invention generally relates to a method for estimating a square of a number and more particularly to estimating the square of negative and positive integers. More particularly still, the invention relates to a flexible technique for estimating a square of an integer in accordance with a desired level of accuracy.
2. Background of the Invention
Many functions performed by digital processing systems such as personal computers and video systems require advanced mathematical calculations. For example, many video systems require the calculation of a "square" of a number. Squaring a number is the mathematical operation by which the number is multiplied by itself. The square of the number 10, for example, is represented as 10.sup.2 which equals 10.times.10 or 100.
Squaring a number is required or recommended for many applications such as for motion estimation in a video processing system. Motion estimation involves determining whether an object has moved from one video frame to the next. One technique for estimating motion involves calculating the sum of square differences between the object at its current location versus its location in a previous frame. That is, the differences between the values of the corresponding "pixels" comprising the image between frames is calculated and then squared. Finally, the squared values are added together and compared to a predetermined threshold value to determine if the object has moved.
Implementing a digital logic circuit to compute accurately a square typically requires a relatively large circuit. The size of a circuit can be measured in terms of "logic gates" or "cell units." A logic gate usually refers to a NAND gate logic unit which is a basic logic unit comprising many digital circuits. A NAND gate comprises one or more switching transistors. By combining NAND gates, and/or other types of logic gates, advanced digital circuits can be created for performing a variety of functions. A cell unit refers to a unit of surface area on an integrated circuit. A single logic gate generally requires approximately 3 cell units. The size of a digital circuit thus can be measured in terms of gates or cell units. This disclosure uses the cell unit to characterize the size of the circuits described herein.
Various techniques have been suggested for determining the square of a number. Some digital systems include a multiplier circuit which actually calculates the square of an input number. Multipliers, however, are undesirably large and expensive and consume a great deal of electrical power. A multiplier that can multiply two 9-bit integers, for example, requires 2,281 cell units for its implementation.
Alternatively, a table look-up method can be implemented for determining the square of a number. In this method, a table stored in memory includes the squares of a plurality of predefined numbers. The squares of the numbers, therefore, are predetermined and loaded into the table Thus, rather than actually calculating the square of a number, the square can be obtained directly from the table. If the square of a number is not stored in the table, the squares of the closest numbers can be used to estimate or calculate the desired result. Table look-up techniques generally require larger circuits for their implementation than multipliers. A table look-up implementation that includes look-ups for 512 squares requires approximately 4300 cell units.
Thus, a technique is needed for determining a square of a number that can be implemented with a smaller circuit and consume less power than previously possible. Despite the advantages offered by such a system, to date no such system is known to exist.